\subsection{Гарантированного в случае раздельных ограничений на помехи}

Рассматриваем схему <<мерим-шагаем>>.
\begin{gather*}
\left\{
\begin{aligned}
x_{k + 1} &= A_k x_k + w_k,\\
y_k &= C_k x_k + v_k.
\end{aligned}
\right.
\\
x_0, w_0, \ldots, w_{N - 1}, v_0, \ldots, v_{N - 1} \text{ --- независимы в совокупности}  \\
\hat x_{k|k-1} \text{ --- достаточная статистика от } x_0, w_0, \ldots, w_{k - 1}, v_0, \ldots, v_{k - 1}, y^*_0, \ldots, y^*_{k - 1},
\end{gather*}
т.е. эта оценка содержит всю информацию о $x_k$ (состоянии системы в момент $k$), содержащуюся в $x_0, w_0, \ldots, w_{k - 1}, v_0, \ldots, v_{k - 1}, y^*_0, \ldots, y^*_{k - 1}$. \\
Рассматриваем марковский процесс с гауссовскими случайными величинами.\\
Вектор состояния:

\begin{multline*}
p(x_0, x_1, \ldots, x_N \mid y^*_0, \ldots, y^*_{N - 1}) = p(x_0, w_0, \ldots, w_{N - 1}, v_0, \ldots, v_{N - 1}, y^*_0, \ldots, y^*_{N - 1}) =\\ 
= \{\text{марк. процесс}\} = p(x_N | x_{N - 1}, y_{N - 1}^*)p(x_{N - 1} | x_{N - 2}, y_{N - 2}^*) \ldots p(x_1 | x_0, y_0)p(x_0) =\\ 
= p(w_{N - 1})p(v_{N - 1})p(w_{N - 2})p(v_{N - 2}) \ldots p(w_0)p(v_0)p(x_0)
\end{multline*}

\begin{gather*}
w_k = x_{k + 1} - A_k x_k, \quad v_k = y_k - C_k x_k\\
p(x_0, x_1, \ldots, x_N) \rightarrow \rm{argmax}, \text{ т.е.}\\
p(w_{N - 1})p(v_{N - 1})p(w_{N - 2})p(v_{N - 2}) \ldots p(w_0)p(v_0)p(x_0) \rightarrow \rm{argmax}
\end{gather*}

\begin{gather*}
p(x_0) = C \exp \left\{ -\frac{1}{2} (x_0 - \overline x_0)' S^{-1}(x_0 - \overline x_0)\right\}\\
p(w_0) = C' \exp \left\{ -\frac{1}{2} W_0' M_0^{-1} W_0 \right\}\\
p(v_0) = C'' \exp \left\{ -\frac{1}{2} V_0' N_0^{-1} V_0 \right\}
\end{gather*}

\begin{gather*}
p(x_0)p(v_0)p(w_0) = \widetilde C \exp \left\{ -\frac{1}{2} ((x_0 - \overline x_0)' S^{-1}(x_0 - \overline x_0) + V_0' N_0^{-1} V_0 + W_0' M_0^{-1} W_0)\right\} \rightarrow \max\\
w_0 = x_1 - A_0 x_0\\
v_0 = y_0 - C_0 x_0\\
V(x, 1) = \min_{x_0} (\| x - A_0x_0\|^2_{M_0^{-1}} + \| y_0 - C_0x_0\|^2_{N_0^{-1}} + \| x - x_0\|^2_{S^{-1}} \mid x_1 = x)
\end{gather*}

Идея динамического программирования: фиксируем правый конец $\rightarrow$ решаем $\rightarrow$ отпускаем правый конец.

\begin{gather*}
V(x, 0) = \| x - \hat x_0 \|^2_{S^{-1}} \text{ --- начальное условие}\\
V(x, k) = \min_{x_0, w_0, \ldots, w_{k - 1}, v_0, \ldots, v_{k - 1}} \left(\sum_{i = 0}^{k - 1} (\|w_i\|^2_{M_i^{-1}} + \|v_i\|^2_{N_i^{-1}}) + \|x_0 - \hat x_0\|^2_{S^{-1}}|x_k = x\right) \\
V(x, k) \text{ --- функция цены на k шаге}
\end{gather*}

Заметим, что для функции цены выполнено {\it полугрупповое свойство}:

\begin{equation}
V(x, k) = \min_{x_{k - 1}, w_{k - 1}, v_{k - 1}} \left((\|w_{k - 1}\|^2_{M_{k - 1}^{-1}} + \|v_{k - 1}\|^2_{N_{k - 1}^{-1}}) + V(x_{k - 1}, k - 1)|x_k = x\right)
\end{equation}

Покажем, что

\begin{gather*}
V(x,k) = \| x - \hat x_{k|k - 1} \|^2_{R^{-1}_{k|k - 1}} + \| y_k - C_k \hat x_{k|k - 1}\|^2_{(N_k + C_k R_{k|k - 1}C'_k)^{-1}} + \varkappa_{k - 1}\\
\varkappa_0 = 0
\end{gather*}

Минимизируем функционал

\begin{gather*}
\Phi(\eta_{\overline{0 \ldots N}}) = \sum_{k = 0}^{N - 1}(\|w_k \|^2_{M_k^{-1}} + \|v_k\|^2_{N_k^{-1}}) + \|x_0 - \overline x_0\|^2_{S^{-1}}\\
\eta_{\overline{0 \ldots k}} = (x_0, w_0, \ldots, w_{k - 1}, v_0, \ldots, v_{k - 1})
\end{gather*}

Пусть на все входящие в систему неопределённости наложены ограничения:

\begin{equation}
\Phi(\eta_{\overline{0 \ldots N}}) = \sum_{k = 0}^{N - 1}(\|w_k \|^2_{M_k^{-1}} + \|v_k\|^2_{N_k^{-1}}) + \|x_0 - \overline x_0\|^2_{S^{-1}} \leq 1
\end{equation}

Тогда можно построить множество достижимости методом динамического программирования путём построения функции цены. Заметим, что

\begin{equation}
\Phi(\eta_{\overline{0 \ldots N}})  \leq 1 \Rightarrow \overline x_0\|^2_{S^{-1}} \leq 1 \Leftrightarrow x_0 \in \mathcal E(x_0, S) \text{ --- эллипсодид}
\end{equation}

Функция цены:

\begin{gather*}
V(x, N) = \min_{\eta_{\overline{0 \ldots N}}} (\Phi(\eta_{\overline{0 \ldots N}}) \mid x_N = x) = \\
= \min_{\eta_{\overline{k \ldots N}}} \left\{ \sum_{l = k}^{N - 1} \| w_l\|^2_{M_l^{-1}} + \sum_{l = k}^{N - 1} \|v_l\|^2_{N_l^{-1}} + V(x_k, k)| x_N = x\right\} \text{ (полугрупповое свойство)}\\
\eta_{\overline{k \ldots N}} = (x_k, w_k, \ldots, w_{N - 1}, v_k, \ldots, v_{N - 1})\\
V(x, 0) = \| x - \overline x_0\|^2_{S^{-1}}, \quad \varkappa_0 = 0 \quad (\overline x_0 = \hat x_{0|-1}, S = R_{0|-1})
\end{gather*}

Покажем по индукции, что:

\begin{equation}
V(x, k) = \| x - \hat x_{k|k - 1} \|^2_{R_{k|k - 1}^{-1}} + \varkappa_k^2
\end{equation}

\begin{gather*}
V(x, k) \rightarrow V(x, k + 1) = ? \quad (\text{ хотим: } \| x - \hat x_{k + 1|k}\|^2_{R_{k + 1|k}} + \varkappa_{k + 1}^2)\\
V(x, k + 1) = \min_{\eta_{\overline{k, k + 1}}} \left\{ \sum_{l = k}^{k + 1 - 1} \| w_l\|^2_{M_l^{-1}} + \sum_{l = k}^{k + 1 - 1} \|v_l\|^2_{N_l^{-1}} + V(x_k, k)| x_{k + 1} = x\right\} = \\
= \min_{x_k, v_k, w_k} \left\{ \| w_k\|^2_{M_k^{-1}} + \|v_k\|^2_{N_k^{-1}} + \| x - \hat x_{k|k - 1} \|^2_{R_{k|k - 1}^{-1}} + \varkappa_k^2| x_{k + 1} = x\right\} =\\
= \{ x_{k + 1} = A_k x_k + w_k, y_k = C_k x_k + v_k\} =\\
=\min_{x_k} \left\{ \| x - A_k x_k\|^2_{M_k^{-1}} + \| y_k - C_k x_k \|^2_{N_k^{-1}} + \| x - \hat x_{k|k - 1} \|^2_{R_{k|k - 1}^{-1}} + \varkappa_k^2\mid x_{k + 1} = x\right\}
\end{gather*}

Приведём сумму к другому виду:

\begin{gather*}
\|y_k - C_k x_k\|^2_{N_k^{-1}} + \| x_k - \hat x_{k|k - 1} \|^2_{R_{k|k - 1}^{-1}} =\\
= \|y_k - C_k \hat x_{k|k - 1} - C_k (x_k - \hat x_{k|k - 1})\|^2_{N_k^{-1}} + \| x_k - \hat x_{k|k - 1} \|^2_{R_{k|k - 1}^{-1}} =\\
= \|y_k - C_k \hat x_{k|k - 1}\|^2_{N_k^{-1}} + \| x_k - \hat x_{k|k - 1} \|^2_{R_{k|k - 1}^{-1} + C'_kN_k^{-1}C_k} - 2(y_k - C_k \hat x_{k|k - 1})'N_k^{-1}C_k(x_k - \hat x_{k|k - 1}) =\\
= \|y_k - C_k \hat x_{k|k - 1}\|^2_{N_k^{-1} - N_k^{-1} C_k(R_{k|k - 1}^{-1} + C'_kN_k^{-1}C_k)^{-1}C'_kN^{-1}_k} + \\
+ \|y_k - C_k \hat x_{k|k - 1}\|^2_{N_k^{-1}C_k(R_{k|k - 1}^{-1} +C'_kN_k^{-1}C_k)^{-1}C'_kN^{-1}_k} + \| x_k - \hat x_{k|k - 1} \|^2_{R_{k|k - 1}^{-1} + C'_kN_k^{-1}C_k} -\\
- 2(y_k - C_k \hat x_{k|k - 1})'N_k^{-1}C_k (R_{k|k - 1}^{-1} +C'_kN_k^{-1}C_k)^{-1}(R_{k|k - 1}^{-1} +C'_kN_k^{-1}C_k) (x_k - \hat x_{k|k - 1}) =\\
= \{ \text{ лемма 1}\} = \\
= \| y_k - C_k x_{k|k - 1}\|^2_{(N_k + C_k R_{k|k - 1} C'_k)^{-1}} +\\
+ \| (x_k - \hat x_{k|k - 1}) - (R^{-1}_{k|k - 1} + C'_kN_k^{-1}C_k)^{-1}C'_kN_k^{-1}(y_k - C_k \hat x_{k|k - 1}) \|^2_{R_{k|k - 1}^{-1} +C'_kN_k^{-1}C_k} = \\
= \left\{ \hat x_{k|k} = \hat x_{k|k - 1} + (R_{k|k - 1}^{-1} +C'_kN_k^{-1}C_k)^{-1}C'_kN_k^{-1}(y_k - C_k \hat x_{k|k - 1}) \right\} = \\
= \| y_k - C_k \hat x_{k|k - 1}\|^2_(N_k + C_kR_{k|k - 1}C'_k)^{-1} + \|x_k - \hat x_{k|k}\|^2_{R_{k|k - 1}^{-1} +C'_kN_k^{-1}C_k} = \\
= \left\{ R_{k|k} = (R_{k|k - 1}^{-1} +C'_kN_k^{-1}C_k)^{-1}\right\}
= \| y_k - C_k \hat x_{k|k - 1}\|^2_{(N_k + C_kR_{k|k - 1}C'_k)^{-1}} + \|x_k - \hat x_{k|k}\|^2_{R_{k|k}^{-1}}
\end{gather*}

Сумма приходит к следующему виду:

\begin{equation}
\| x - A_k x_k\|^2_{M_k^{-1}} + \| y_k - C_k \hat x_{k|k - 1}\|^2_{(N_k + C_kR_{k|k - 1}C'_k)^{-1}} + \|x_k - \hat x_{k|k}\|^2_{R_{k|k}^{-1}}
\end{equation}

Распишем сумму первого и третьего слагаемых.

\begin{gather*}
\| x - A_k \hat x_{k|k} - A_k(x_k - \hat x_{k|k})\|^2_{M_k^{-1}} + \|x_k - \hat x_{k|k}\|^2_{R_{k|k}^{-1}} =\\
= \| x - A_k \hat x_{k|k}\|^2_{M_k^{-1} - M_k^{-1}A_k(R_{k|k}^{-1} + A'_kM_k^{-1}A_k)^{-1}A'_kM^{-1}_k} + \| x - A_k \hat x_{k|k}\|^2_{M_k^{-1}A_k(R_{k|k}^{-1} + A'_kM_k^{-1}A_k)^{-1}A'_kM^{-1}_k} + \\
+\|x_k - \hat x_{k|k}\|^2_{R_{k|k}^{-1}} + \|x_k - \hat x_{k|k}\|^2_{A'_kM_k^{-1}A_k} - 2 (x - A_k\hat x_{k|k})'M^{-1}_kA_k(x_k - \hat x_{k|k}) = \\
=\{\text{лемма 1} \} = \\
= \| x - A_k \hat x_{k|k}\|^2_{(M_k + A_kR_{k|k}A'_k)^{-1}} + \\
+ \left\| x_k - \hat x_{k|k} - (R_{k|k}^{-1} + A'_kM_k^{-1}A_k)^{-1}A'_kM^{-1}_k(x - A_k \hat x_{k|k})\right\|^2_{R_{k|k}^{-1} + A'_kM_k^{-1}A_k} = \\
= \left\{ x_{k + 1|k} = A_k \hat x_{k|k}; R_{k + 1|k} = A_k R_{k|k}A'_k + M_k\right\} = \\
\| x - x_{k + 1|k}\|^2_{R_{k + 1|k}^{-1}} + \left\|x_k - \left[\hat x_{k|k} + (R_{k|k}^{-1} + A'_kM_k^{-1}A_k)^{-1}A'_kM^{-1}_k(x - A_k \hat x_{k|k}) \right]\right \|^2_{R_{k|k}^{-1} + A'_kM_k^{-1}A_k}
\end{gather*}

Итак, получим

\begin{multline}
V(x, k + 1) = \min_{x_k} \left\{ \|x - x_{k + 1|k}\|^2_{R^{-1}_{k + 1|k}} + \|y_k - C_k \hat x_{k|k - 1}\|^2_{(N_k + C_kR_{k|k - 1}C'_k)^{-1}} + \right.\\
\left. + \left\|x_k - \left[ \hat x_{k|k} + (R_{k|k}^{-1} + A'_kM_k^{-1}A_k)^{-1}A'_kM^{-1}_k(x - A_k \hat x_{k|k}) \right] \right\|^2_{R_{k|k}^{-1} + A'_kM_k^{-1}A_k} + \varkappa_k^2 \mid x_{k + 1} = x \right\} = \\
= \| x - x_{k + 1|k}\|^2_{R^{-1}_{k + 1|k}} + \|y_k - C_k\hat x_{k|k - 1}\|^2_{(N_k + C_kR_{k|k - 1}C'_k)^{-1}} + \varkappa_k^2 = \|x - x_{k + 1|k}\|^2_{R_{k + 1|k}^{-1}} + \varkappa_{k + 1}^2
\end{multline}

\begin{gather*}
V(x, 0) = \| x - \overline x_0\|^2_{S^{-1}}, \quad x_0 = 0\\
V(x, k) = \| x - \hat x_{k|k - 1} \|^2_{R_{k|k - 1}^2} + \varkappa_k^2\\
\varkappa_k^2 = \sum_{l = 0}^{k - 1} \|y_l - C_l\hat x_{l|l - 1} \|^2_{(N_l + C_lR_{l|l - 1}C'_l)^{-1}}  
\end{gather*}

Ограничения:

\begin{gather}
\Phi(\eta_{\overline{0 \ldots N}}) \leq 1\\
V(x, N) = \min_{\eta_{\overline{0 \ldots N}}} (\Phi(\eta_{\overline{0 \ldots N}})|x_N = x)
\end{gather}

Следовательно, сечение функции цены на определенном уровне можно записать так:

\begin{equation}
V(x, N) \leq 1 \Leftrightarrow \| x - \hat x_{N|N - 1} \|^2_{R^{-1}_{N|N - 1}} \leq 1 - \varkappa_N^2 
\end{equation}

Вспомним, что  $x$ имеет смысл $x_N$, тогда

\begin{equation}
x_N \in \mathcal E(\hat x_{N|N - 1}, (1 - \varkappa_N^2)R_{N|N - 1}) \text{ ---  гарантированная оценка}
\end{equation}

\begin{stm}{\rm (без доказательства)}
Константа $1 - \varkappa_N^2$ всегда положительна.
\end{stm}

Таким образом, чем больше $\varkappa_N^2$, тем меньше эллипсоид, следовательно, чем более информативно измерение, тем больше $\varkappa_N^2$, а значит, тем быстрее сойдемся в точку (даже если ошибка $R_{N|N - 1}$ фиксирована, т.е. не зависит от  $N$, и положительна).

\begin{equation}
x_N \in \hat x_{N|N - 1} + \sqrt{1 - \varkappa_N^2}\mathcal E(0, R_{N|N - 1})
\end{equation}

\begin{gather*}
\hat x_{N|N - 1} \text{ --- центр эллипсоида},\\
\sqrt{1 - \varkappa_N^2} \text{ --- размер эллипсоида},\\
R_{N|N - 1} \text{ --- форма эллипсоида}.
\end{gather*}

\par
В каком смысле точечная оценка $\hat x_{N|N - 1}$ будет хорошей оценкой? Т.е. какую оценку нужно искать, чтобы получить $\hat x_{N|N - 1}$?
\par
У нас нет статистической информации о расположении $x_N$ внутри эллипсоида, поэтому предполагаем самое плохое для ограниченного носителя --- равномерное распределение. Тогда в качестве точечной оценки можно взять центр масс множества (центр Чебышёва); однако в невыпуклом множестве центр масс может лежать вне множества (этот вопрос решается с помощью численных методов).

\begin{df}
Вектор  $z \in \mathbb R^l$ называется {\it чебышёвским центром множества $A$}, а число  $\delta$  --- {\it  чебышёвским радиусом}, если

\begin{equation}
\min_{p \in \mathbb R^l} \max_{x \in A} \left\{ \| x - p\|^2 \right\} = \max_{x \in A} \| x - z \|^2 = \delta^2
\end{equation}  
\end{df}

У центрально--симметричного множества центр симметрии совпадает с чебышёвским центром.\\
$\delta$ равна половине длины максимальной диагонали.
\par
Возьмём в качестве множества $A$ эллипсоид $\mathcal E (\hat x_{N|N - 1}, (1 - \varkappa_N^2)R_{N|N - 1})$. Тогда чебышёвский радиус $\delta$ --- большая полуось, чебышёвский центр $z = \hat x_{N|N - 1}$.\\
Для достаточно больших $N$ можем заменить $R_{N|N - 1} \rightarrow R$.  Малая полуось --- радиус максимального вписанного шара. Большая полуось --- радиус минимального описанного шара.